class code3 {
    public List<String> topKFrequent(String[] words, int k) {
        //1.创建哈希表统计
        Map<String,Integer> hash = new HashMap<>();
        for(String s:words) {
            hash.put(s,hash.getOrDefault(s,0)+1);
        }

        //2.创建堆(小根堆)
        PriorityQueue<Pair<String,Integer>> heap = new PriorityQueue<>(
                (a,b)-> {
                    if(a.getValue().equals(b.getValue())) {
                        return b.getKey().compareTo(a.getKey());
                    }
                    return a.getValue()-b.getValue();
                }
        );

        //3.top k排序
        for(Map.Entry<String,Integer> e: hash.entrySet()) {
            heap.offer(new Pair<>(e.getKey(), e.getValue()));
            if(heap.size()>k) {
                heap.poll();
            }
        }
        //4.返回结果
        List<String> ret = new ArrayList<>();
        while(!heap.isEmpty()) {
            ret.add(heap.poll().getKey());
        }

        //逆序
        Collections.reverse(ret);
        return ret;
    }
}